package singleList;

import listinterface.IList;

import java.util.List;

//import ListIndexOutOfBoundsException;
public class MySingleList implements IList {
    public static class ListNode{
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }
    public ListNode head;
    public int listsize;

    public void createList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        ListNode node6 = new ListNode(67);
        ListNode node7 = new ListNode(78);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        this.head = node1;

    }
    public void createList2(){
        ListNode node1 = new ListNode(13);
        ListNode node2 = new ListNode(24);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(46);
        ListNode node5 = new ListNode(58);
        ListNode node6 = new ListNode(66);
        ListNode node7 = new ListNode(75);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        this.head = node1;

    }
    @Override
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        head = newNode;
        listsize++;
    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);

        if (head == null){
            head = newNode;
            listsize++;
            return;
        }
        ListNode cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
        listsize++;
    }

    @Override
//    public void addIndex(int index, int data) {
////        checkIndexOfAdd(index);
//        ListNode newNode = new ListNode(data);
//        if (index == 0){
//            addFirst(data);
//            return;
//        }
//        if (index == size()){
//            addLast(data);
//            return;
//        }
//        ListNode cur = findIndex(index);
//        newNode = cur.next;
//        cur.next = newNode;
//        listsize++;
//
//    }
    public void addIndex(int index, int data)
            throws ListIndexOutOfBoundsException {

        checkIndexOfAdd(index);

        ListNode node = new ListNode(data);

        if(index == 0) {
            addFirst(data);
            return;
        }

        if(index == size()) {
            addLast(data);
            return;
        }

        ListNode cur = findIndex(index);

        node.next = cur.next;

        cur.next = node;

        listsize++;
    }

    //写一个方法
    private ListNode findIndex(int index){
        ListNode cur = head;
        int count = 0;
        while(count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    private void checkIndexOfAdd(int index) {
        if (index < 0 || index > size()) {
            throw new ListIndexOutOfBoundsException("插入Index的位置不合法");
        }
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null) {
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if (head == null){
            return;
        }
        if (head.val == key){
            head = head.next;
            listsize--;
        }
        ListNode cur = findNod(key);
        if (cur == null){
            System.out.println("没有你要找的数据");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
        listsize--;

    }

    //找到 key 的前一个节点
    private ListNode findNod(int key){
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    @Override
    public void removeAllKey(int key) {
        if (head == null){
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null) {
            if (cur.val == key){
                prev.next = cur.next;
                listsize--;
            } else{
                prev = cur;
            }
            cur = cur.next;
        }
        if (head.val == key){
            head = head.next;
            listsize--;
        }
    }

    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;

    }

    @Override
    public void clear() {
        head = null;
        listsize = 0;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null){
            System.out.println(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null){
            System.out.println(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //反转数组
    public ListNode reverse(){
        if (head == null){
            return null;
        }
        if (head.next == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur =curN;
        }
        return head;
    }

    //查找链表的中间节点
    public ListNode middleNode(){
        if (head == null){
            return head;
        }
        int len = size();
        int index = len/2;
        ListNode cur = head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public ListNode middleNode(ListNode head){
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    // 返回倒数第 k 个节点
    public int KthToLast(int k) {
        int len = size();
        if (k <= 0 || k > len) {
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while (count != k-1){
            fast = fast.next;
            count++;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
    //传入两个升序的有序列表 ， 将两个列表合并为一个有序列表
    public ListNode mergeTwoLists(ListNode headA,
                                  ListNode headB) {
        ListNode newNode = new ListNode(-1);
        ListNode temp = newNode;
        while (headA != null || headB != null){
            if (headA.val < headB.val) {
                temp.next = headA;
                headA = headA.next;
                temp = temp.next;
            } else{
                temp.next = headB;
                headB = headB.next;
                temp = temp.next;
            }
            if(head != null) {
                temp.next = headB;
            }else {
                temp.next = headA;
            }
        }
        return newNode.next;
    }

    //判断一个链表是否是回文
    public boolean chPalindrome(ListNode list){
        if (head == null){
            return false;
        }
        if (head.next == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转后半部分链表
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        //判断是否是回文

        while (head != slow){
            if (head.val != slow.val){
                return false;
            }
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    //找到相交链表的相交节点
    public ListNode getIntersectionNode(ListNode headA,
                                        ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;

        int len1 = 0;
        int len2 = 0;
        while(pl != null){
            pl = pl.next;
            len1++;
        }
        while(ps != null){
            ps = ps.next;
            len2++;
        }
        int len = len1 - len2;
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = len2 - len1;
        }
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        if (pl == null) {//说明没有相遇
            return null;
        }
        return pl;
    }
    //判断链表是否是一个环形链表
    public boolean hasCycle() {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    //找到环形链表环型的入口
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            //没有入环
            return null;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
